public class Text {
    //给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
    public int peakIndexInMountainArray(int[] arr) {
        //数组有二段性  分为递减和递增两部分
        //有二段性 就可以用二分查找
        int left = 0,right = arr.length - 1;
        while(left < right) {
            int mid = left +(right - left + 1) /2;   //这里必须加1   不然数组是奇数个元素的时候就会死循环
            if(arr[mid] > arr[mid - 1]) {
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    public int searchInsert(int[] nums, int target) {
        //二分查找
        int left = 0, right = nums.length - 1;
        while(left < right) {
            //算中点
            int mid = left + (right - left) /2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[right] < target) return right + 1;
        return right;
    }
    //二分查找求一个数的平分根
    public int mySqrt(int x) {
        if(x < 1) return 0;

        long left = 1,right = x;
        while(left < right) {
            long mid = left + (right - left + 1 ) / 2;
            if(mid * mid <= x) {
                left = mid;
            }else{
                right = mid - 1;
            }
        }
        return (int)right;
    }
    public static void main(String[] args) {

    }
}
